//和大于等于 target 的最短子数组
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int left=0;
        int right=left;
        int sum=0;
        int res=INT_MAX;
        while(right<nums.size())
        {
            sum+=nums[right];
            while(sum>=target)
            {
                res=min(res,right-left+1);
                sum-=nums[left];
                left++;
            }
            right++;
        }
        if(res==INT_MAX) return 0;
        return res;
    }
};


//乘积小于k的子数组
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) 
    {
        // k = 1 和 k = 0 的情况是无解的
        if(k == 0 || k == 1)
            return 0;
        int left = 0, right= 0;
        int mul = 1, count = 0;
        while(right < nums.size()) 
        {
            mul*= nums[right];
            while(mul>= k) 
            {  
                // 非必要不动左边界，不满足条件时，left 才挪个窝
                // 也就是说，窗口是慢慢缩小到满足条件的最大情况，而不是扩大到最大情况
                mul /= nums[left];
                left++;
            }
            //right是一个一直在更新的右端点，以i这个数为端点且符合条件的子数组个数
            //就是从[right], [right - 1, right], [right-2, right-1,right], ......, 
            //[left, left+1, .... , right-1,right];
            //也就是从right到left的子数组长度，
            count+= right - left + 1;
            right++;
        }
        return count;
    }
};

//数组中和为0的三个数
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>>res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++)
        {
            if(i>0 && nums[i]==nums[i-1]) continue;

            int sum=-nums[i];
            int left=i+1;
            int right=nums.size()-1;
            while(left<right)
            {
                if (left > i + 1 && nums[left - 1] == nums[left]) {
                    ++left;
                    continue;
                }
                
                if(nums[left]+nums[right]>sum)
                {
                    right--;
                }
                else if(nums[left]+nums[right]==sum)
                {
                    res.push_back({nums[i],nums[left],nums[right]});
                    left++;
                }
                else
                {
                    left++;
                }
            }
        }
        return res;
    }
};